Grau (teoria de grafs)

Un graf amb vèrtexs etiquetats segons el seu grau. El *vèrtex aïllat* s'etiqueta amb 0, ja que no és adjacent a cap altre vèrtex.

En teoria de grafs, el grau o valència d'un vèrtex és el nombre d'arestes que hi incideixen, amb els bucles comptats dues vegades.^[1] El grau d'un vèrtex v es denota grau(v), g(v) o gr(v) (tot i que també es fa servir δ(v), i de l'anglès d(v) i deg(v)). El grau màxim d'un graf G, denotat com Δ(G), i el grau mínim d'un graf G, denotat com δ(G), són respectivament els graus màxim i mínim dels seus vèrtexs. Al graf de la dreta, el grau màxim és 3 i el grau mínim és 0. En un graf regular tots els graus són iguals, i per tant es pot parlar del grau del graf.

↑ Diestel, Reinhard. Graph Theory (en anglès). 3a ed.. Berlin, New York: Springer-Verlag, 2005, p.5. ISBN 978-3-540-26183-4.

[1] Diestel, Reinhard. Graph Theory (en anglès). 3a ed.. Berlin, New York: Springer-Verlag, 2005, p.5. ISBN 978-3-540-26183-4.

[1]